package Sequence;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test0090 {
    public static void main(String[] args) {
        new Solution0090_1().subsetsWithDup(new int[]{1,2,2});
    }
}

class Solution0090_1 {
    List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        ans.add(new ArrayList<>());

        for (int i = 0; i < nums.length; i=next(nums,i)) {
            backtrack(nums,i,new ArrayList<>());
        }

        return ans;
    }

    public void backtrack(int[] nums,int index,List<Integer> list){
        int length = nums.length;
        if(index== length){
            ans.add(new ArrayList<>(list));
        }else {
            list.add(nums[index]);
            for (int i = index+1; i <= length; i=next(nums,i)) {
                backtrack(nums,i,list);
            }
            list.remove(list.size()-1);
        }
    }

    public int next(int[] nums,int index) {
        int length = nums.length;
        if (index==length) return length+1;
        int num = nums[index];
        while(index<length&&num==nums[index]) index++;
        return index;
    }
}
